//给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之
//外其余各元素的乘积。 
//
// 
//
// 示例: 
//
// 输入: [1,2,3,4]
//输出: [24,12,8,6] 
//
// 
//
// 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。 
//
// 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。 
//
// 进阶： 
//你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。） 
// Related Topics 数组 前缀和 
// 👍 1000 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class ProductOfArrayExceptSelf {
    public static void main(String[] args) {
        Solution solution = new ProductOfArrayExceptSelf().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 不让用除法，而且时间复杂度为N，空间复杂度没有要求
         * 进阶：时间空间复杂度都 <= N ，且不能用除法
         */
        public int[] productExceptSelf1(int[] nums) {
            int len = nums.length;
            int[] output = new int[len];
            int n = 1;
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                if (nums[i] != 0){
                    n *= nums[i];
                } else{
                    list.add(i);
                    if (list.size()>1) return output;//提前终止
                }
            }

            if (list.size() == 1){//有一个零的话只有在下标处不为0
                output[list.get(0)] = n;
                return output;
            }

            for (int i = 0; i < output.length ; i++) {
                output[i] = n/nums[i];// 原则上是不能用除法的
            }
            return output;
        }


        /**
         * 不用除法
         * 当前位置的返回值 = 当前位置左边的乘积 * 当前位置右边的乘积
         * 可以使用两个数组来保存乘积
         *
         * 空间优化：使用原始数组以及out数组完成统计：
         * 第一遍让out储存左边的值，第二遍直接将最终结果写入out数组
         */
        public int[] productExceptSelf(int[] nums) {
            int len = nums.length;
            int k = 1;
            int[] out = new int[len];
            for (int i = 0; i < len ; i++) {//存左边的乘积
                out[i] = k;
                k *= nums[i];
            }
            k = 1;
            for (int i = len-1; i >=0 ; i--) {//乘上右边的乘积
                out[i] *= k;
                k *= nums[i];
            }
            /*int[] left = new int[len];
            int[] right = new int[len];
            int k = 1;
            for (int i = 0; i < len; i++) {
                left[i] = k;
                k*=nums[i];
            }
            k = 1;
            for (int i = len-1 ; i >= 0 ; i--) {
                right[i] = k;
                k*=nums[i];
            }

            for (int i = 0; i < len; i++) {
                out[i] = left[i]*right[i];
            }*/
            return out;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}